package com.mdnote.algorithm;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/9
 * @description 普利姆算法
 */
public class PrimAlgorithm {

    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        PrimAlgorithm primAlgorithm = new PrimAlgorithm();

        MGraph mGraph = new MGraph(7);
        mGraph.setVertex(new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'});
        mGraph.setWeights(new int[][]{
                {  0,   5,   7, INF, INF, INF,   2},
                {  5,   0, INF,   9, INF, INF,   3},
                {  7, INF,   0, INF,   8, INF, INF},
                {INF,   9, INF,   0, INF,   4, INF},
                {INF, INF,   8, INF,   0,   5,   4},
                {INF, INF, INF,   4,   5,   0,   6},
                {  2,   3, INF, INF,   4,   6,   0}
        });
        primAlgorithm.priom(mGraph);
    }

    /**
     * 核心代码
     * @param mGraph 图
     */
    private void priom(MGraph mGraph) {

        // 记录访问记录
        int[] isVisited = new int[mGraph.vertexCount];
        // 我们先处理第一个元素
        int h1 = -1;
        int h2 = -1;
        int totalWeight = 0;
        // 随便添加一个元素到结果集中
        isVisited[0] = 1;
        // 思路如下：遍历真个领接矩阵，不断从里面挑选出以访问元素周围的最小元素
        // 探测n - 1次
        for (int k = 1; k < mGraph.vertex.length; k++) {
            // 寻找领接矩阵中的访问过的元素周围最近的节点
            int minWeight = INF;
            for (int i = 0; i < mGraph.weights.length; i++) {
                for (int j = 0; j < mGraph.weights[0].length; j++) {
                    if (mGraph.weights[i][j] != INF && isVisited[i] == 1 && isVisited[j] == 0 && minWeight >= mGraph.weights[i][j]) {
                        h1 = i;
                        h2 = j;
                        minWeight = mGraph.weights[i][j];

                    }
                }
            }
            System.out.println(mGraph.vertex[h1] + " ->" + mGraph.vertex[h2]);
            totalWeight += minWeight;
            isVisited[h2] = 1;
        }

        System.out.println("总权值：" + totalWeight);
    }

    private static class MGraph {

        private int vertexCount;
        private char[] vertex;
        private int[][] weights;

        public MGraph(int vertexCount) {
            this.vertexCount = vertexCount;
        }

        public void setVertex(char[] vertex) {
            this.vertex = vertex;
        }

        public void setWeights(int[][] weights) {
            this.weights = weights;
        }
    }
}
